/*
	
	MultiLevelLayoutPlugin for Cytoscape (http://www.cytoscape.org/) 
	Copyright (C) 2007 Pekka Salmela

	This program is free software; you can redistribute it and/or
	modify it under the terms of the GNU General Public License
	as published by the Free Software Foundation; either version 2
	of the License, or (at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.
	
	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
	
 */

package multilevelLayoutPlugin;

import giny.model.Edge;
import giny.model.Node;

import java.awt.geom.Point2D;
import java.awt.geom.Point2D.Double;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

import mTree.MTree;
import mTree.MTreeNode;
import utility.GraphUtility;
import cytoscape.CyNetwork;
import cytoscape.Cytoscape;
import cytoscape.data.CyAttributes;

/**
 * Class used to calculate a nice layout for a graph using a heavily tuned
 * force-directed placement algorithm by C. Walshaw (2003).
 * 
 * @author Pekka Salmela
 * 
 */
public class EnhancedForceDirectedLayout {

    private static final int TIMEOUT_MS = 500000;

    /**
     * Natural Spring Length for this level.
     */
    private final double k;

    /**
     * Grid size used to find out the local neighborhood
     * 
     * of a node.
     */
    private final int R;

    private final MultilevelConfig multilevelConfig;

    private CyNetwork network;

    private NodePositionManager posManager;

    /**
     * Class constructor.
     * 
     * @param previousNaturalSpringLength
     *            Ideal length of the edges on the previous graph level.
     * @param level
     *            The graph level the layout calculation is done for.
     * @param network
     *            The graph view that the layout is done for.
     * @param posManager
     *            The position manager used to store node positions.
     */
    public EnhancedForceDirectedLayout(
            final double previousNaturalSpringLength, final double level,
            final CyNetwork network, final NodePositionManager posManager,
            final MultilevelConfig multilevelConfig) {
        k = (Math.sqrt(multilevelConfig.springLengthConstant))
                * previousNaturalSpringLength;
        R = (int) (2.0 * (level + 1.0) * k);
        this.multilevelConfig = multilevelConfig;
        this.network = network;
        this.posManager = posManager;
        CTimesKSquared = multilevelConfig.C * k * k;
    }

    /**
     * Calculates a nice layout for the graph given in the constructor using an
     * tuned version of force-directed placement layout.
     */
    @SuppressWarnings("unchecked")
    public void doLayout() {
        final long startTime = System.currentTimeMillis();
        final HashSet<Node> neighboringNodesOfV = new HashSet<Node>();
        final HashSet<Edge> edgesConnectedToV = new HashSet<Edge>();
        final CyAttributes nodeAttributes = Cytoscape.getNodeAttributes();

        boolean converged = false;
        double t = k;
        MTree mTree = null;
        ClusteringCoefficientManager ccm = null;
        List<Node> closeNodes = new ArrayList<Node>();

        if (multilevelConfig.clusteringEnabled) {
            ccm = new ClusteringCoefficientManager();
            ccm.setAllCCs(network);
        }

        // Repeat as long as there is enough movement
        while (!converged) {
            converged = true;

            if (multilevelConfig.mTreeEnabled) {
                mTree = GraphUtility.constructMTree(network.nodesIterator(),
                        posManager);
            }

            final Iterator<Node> iterator = network.nodesIterator();
            while (iterator.hasNext()) {
                final Node v = iterator.next();
                // FIND NODES IN A RANGE OF R FROM NODE v
                // start = System.currentTimeMillis();
                closeNodes = new ArrayList<Node>();
                if (multilevelConfig.mTreeEnabled) {
                    // get close nodes from m-tree
                    mTree.getRoot().getRange(new MTreeNode(v), R, closeNodes,
                            0, posManager);
                } else {
                    // get close nodes with brute force
                    closeNodes = GraphUtility.getCloseNodes(v,
                            network.nodesIterator(), posManager, R);
                }

                // FIND NODES CONNECTED TO NODE v
                edgesConnectedToV.clear();
                final int[] edgeIndices = network.getAdjacentEdgeIndicesArray(
                        v.getRootGraphIndex(), true, true, true);
                for (int i = 0; i < edgeIndices.length; i++) {
                    edgesConnectedToV.add(network.getEdge(edgeIndices[i]));
                }
                neighboringNodesOfV.clear();
                for (final Edge e : edgesConnectedToV) {
                    if (!e.getSource().equals(v)) {
                        neighboringNodesOfV.add(e.getSource());
                    }
                    if (!e.getTarget().equals(v)) {
                        neighboringNodesOfV.add(e.getTarget());
                    }
                }

                // CALCULATE REPULSIVE FORCES
                final Double DispVector = new Point2D.Double(0, 0);
                double diffLength, uWeight, fRep, newX, newY;
                Double DiffVector;
                // iterate over nodes in a range of R
                for (final Node u : closeNodes) {
                    if (u != v) {
                        DiffVector = getDifferenceVector(u, v, posManager);
                        diffLength = getVectorLength(DiffVector);

                        // do the nodes share the exact same position
                        if (diffLength == 0.0) {
                            posManager.setPosition(u.getRootGraphIndex(),
                                    posManager.getX(u.getRootGraphIndex())
                                            + plusOrMinusOne() * 0.001 * k,
                                    posManager.getY(u.getRootGraphIndex())
                                            + plusOrMinusOne() * 0.001 * k);
                            DiffVector = getDifferenceVector(u, v, posManager);
                            diffLength = getVectorLength(DiffVector);
                        }
                        if (diffLength == 0.0) {
                            // if still 0, then terminate with current
                            // parameters
                            throw new IllegalStateException(
                                    "Illegal state, try with different parameters.");
                        }
                        // get the weight of the node
                        uWeight = 1.0;
                        if (nodeAttributes.getIntegerAttribute(
                                u.getIdentifier(), "ml_weight") != null) {
                            uWeight = nodeAttributes.getIntegerAttribute(
                                    u.getIdentifier(), "ml_weight");
                        }

                        // calculate actual repulsive force
                        fRep = forceRepulsive(diffLength, uWeight);

                        if (multilevelConfig.clusteringEnabled) {
                            if (neighboringNodesOfV.contains(u)) {
                                if (ccm.getCC(u.getRootGraphIndex()) >= multilevelConfig.minimumCC) {
                                    fRep = fRep
                                            / (1.0 + ccm.getCC(u
                                                    .getRootGraphIndex())
                                                    * multilevelConfig.ccPower);
                                }
                            }
                        }
                        // set the displacement
                        newX = DispVector.getX()
                                + (DiffVector.getX() / diffLength) * fRep;
                        newY = DispVector.getY()
                                + (DiffVector.getY() / diffLength) * fRep;
                        DispVector.setLocation(newX, newY);
                    }
                }

                // start = System.currentTimeMillis();

                // CALCULATE ATTRACTIVE FORCES BETWEEN CONNECTED NODES
                double fAttr;
                // iterate over nodes connected to v
                for (final Node n : neighboringNodesOfV) {
                    DiffVector = getDifferenceVector(n, v, posManager);
                    diffLength = getVectorLength(DiffVector);
                    // do the nodes share the exact same position
                    if (diffLength == 0.0) {
                        posManager.setPosition(n.getRootGraphIndex(),
                                posManager.getX(n.getRootGraphIndex())
                                        + plusOrMinusOne() * 0.001 * k,
                                posManager.getY(n.getRootGraphIndex())
                                        + plusOrMinusOne() * 0.001 * k);
                        DiffVector = getDifferenceVector(n, v, posManager);
                        diffLength = getVectorLength(DiffVector);
                    }
                    if (diffLength == 0.0) {
                        // if still 0, then terminate with current parameters
                        throw new IllegalStateException(
                                "Illegal state, try with different parameters.");
                    }
                    // calculate actual attractive force
                    fAttr = forceAttractive(diffLength);

                    if (multilevelConfig.clusteringEnabled) {
                        if (ccm.getCC(n.getRootGraphIndex()) >= multilevelConfig.minimumCC) {
                            fAttr = fAttr
                                    * (1.0 + ccm.getCC(n.getRootGraphIndex())
                                            * multilevelConfig.ccPower);
                        }
                    }
                    // set the displacement
                    newX = (DispVector.getX() + (DiffVector.getX() / diffLength)
                            * fAttr);
                    newY = (DispVector.getY() + (DiffVector.getY() / diffLength)
                            * fAttr);
                    DispVector.setLocation(newX, newY);
                }

                // attTime += System.currentTimeMillis() -start;

                // REPOSITION v
                // first, save old position
                final Double vOldPosition = new Point2D.Double(
                        posManager.getX(v.getRootGraphIndex()),
                        posManager.getY(v.getRootGraphIndex()));
                final double dispLength = getVectorLength(DispVector);
                if (dispLength != 0.0) {
                    posManager.setX(
                            v.getRootGraphIndex(),
                            posManager.getX(v.getRootGraphIndex())
                                    + (DispVector.getX() / dispLength)
                                    * Math.min(t, dispLength));
                    posManager.setY(
                            v.getRootGraphIndex(),
                            posManager.getY(v.getRootGraphIndex())
                                    + (DispVector.getY() / dispLength)
                                    * Math.min(t, dispLength));
                }
                // calculate the amount of movement
                DiffVector = new Point2D.Double(
                        (vOldPosition.getX() - posManager.getX(v
                                .getRootGraphIndex())),
                        (vOldPosition.getY() - posManager.getY(v
                                .getRootGraphIndex())));
                // if movement is above treshold => not converged
                if (getVectorLength(DiffVector) > k
                        * multilevelConfig.tolerance) {
                    converged = false;
                }

            }

            // reduce the temperature to limit the maximum movement
            t = cool(t);
            if (System.currentTimeMillis() - startTime > TIMEOUT_MS) {
                System.out
                        .println("TIMEOUT OCCURED: Stopping with current layout.");
                converged = true;
            }
        }
        posManager = null;
        network = null;
        // System.out.println("grid: " + gridTime + " rep: " + repTime +
        // " attr: " + attTime);
    }

    /**
     * Calculates the difference vector of vectors u and v, namely vector u-v.
     * 
     * @param u
     *            First vector.
     * @param v
     *            Second vector.
     * @return Vector u-v.
     */
    private static Point2D.Double getDifferenceVector(final Node u,
            final Node v, final NodePositionManager pm) {
        return new Point2D.Double(
                (pm.getX(u.getRootGraphIndex()) - pm.getX(v.getRootGraphIndex())),
                (pm.getY(u.getRootGraphIndex()) - pm.getY(v.getRootGraphIndex())));
    }

    /**
     * Calculates the distance from origo to point p; that is, the distance of
     * vector (p.x, p.y).
     * 
     * @param p
     * @return
     */
    private static double getVectorLength(final Point2D.Double p) {
        final double distance = p.distance(0.0, 0.0);
        if (java.lang.Double.isNaN(distance)) {
            System.out.println(p);
            throw new IllegalStateException("We have a NaN");
        }
        return distance;
    }

    /**
     * Calculates the next step of the cooling schedule.
     * 
     * @param previous
     * @return The next step of the cooling schedule.
     */
    private double cool(final double previous) {
        return multilevelConfig.T * previous;
    }

    private final double CTimesKSquared;

    /**
     * Calculates the amount of repulsive force between two nodes.
     * 
     * @param x
     *            Distance between the two nodes.
     * @param w
     *            Weight of the node the new position is calculated for.
     * @return Amount of repulsive force.
     */
    private double forceRepulsive(final double x, final double w) {
        if (java.lang.Double.isNaN(x)) {
            throw new IllegalStateException("Parameter x was NaN");
        }
        if (x == 0.0) {
            throw new IllegalStateException("Parameter x was 0");
        }
        return -1.0 * (w * CTimesKSquared / x);
    }

    /**
     * Calculates the amount of attractive force between two nodes.
     * 
     * @param x
     *            Distance between the two nodes.
     * @return Amount of attractive force.
     */
    private double forceAttractive(final double x) throws IllegalStateException {
        if (java.lang.Double.isNaN(x)) {
            throw new IllegalStateException("Parameter x was NaN");
        }
        return multilevelConfig.A * (x * x) / k;
    }

    /**
     * Returns the ideal edge length used in calculation.
     * 
     * @return Ideal edge length.
     */
    public double getK() {
        return k;
    }

    /**
     * Returns 1 or -1 with equal probability.
     * 
     * @return 1 or -1, toss a coin to guess which one.
     */
    private double plusOrMinusOne() {
        if (Math.random() < 0.5) {
            return 1.0;
        } else {
            return -1.0;
        }
    }
}
